Dimostrare che: \(\sum_{i = 0}^n 2 i + 1 = ( n + 1 )^2\) per ogni \(n \in \mathbb{N}\).
Dimostrazione per induzione su \(n \in \mathbb{N}\) (equivalentemente, su \(n \geq 0\)).
\(P ( n )\) è \(\sum_{i = 0}^{n} 2 i + 1 = ( n + 1 )^2\).
Caso base (\(n= 0\)) \(P(0)\) è \(\sum_{i = 0}^{0} 2 i + 1 = ( 0 + 1 )^2\). Verifichiamo:
\(\sum_{i=0}^0 2i+1 = 2 \cdot 0 + 1 = 1\) e \((0+1)^2 = 1^2 = 1 ,\)
quindi \(P(0)\) è vera.
Passo induttivo (\(P(n) \to P(n+1)\)) \(P(n)\) è \(\sum_{i = 0}^{n} 2 i + 1 = ( n + 1 )^2\) (Ipotesi induttiva).
\(P(n+1)\) è \(\sum_{i = 0}^{n+1} 2 i + 1 = ((n+1) + 1 )^2\).
| \( \sum_{i = 0}^{n + 1 } 2 i + 1 \) | \( = ( \sum_{i = 0}^n 2 i + 1 ) + (2 ( n + 1 ) + 1) \) |
|---|---|
| \( = ( n + 1 )^2 + 2 ( n + 1 ) + 1 \text{ [per ip. ind.] } \) | |
| \( = ( ( n + 1 ) + 1 )^2. \) |
Dimostrare che: \(\sum_{i = 0}^n 2 i + 1 = ( n + 1 )^2\) per ogni \(n \in \mathbb{N}\).
Passo induttivo (\(P(n) \to P(n+1)\))
\(P(n)\) è \(\sum_{i = 0}^{n} 2 i + 1 = ( n + 1 )^2\) (Ipotesi induttiva).
\(P(n+1)\) è \(\sum_{i = 0}^{n+1} 2 i + 1 = ( (n+1) + 1 )^2\).
| \( \sum_{i = 0}^{n + 1 } 2 i + 1 \) | \( = ( \sum_{i = 0}^n 2 i + 1) + (2 ( n + 1 ) + 1) \) |
|---|---|
| \( = ( n + 1 )^2 + 2 ( n + 1 ) + 1 \) | |
| \( = n^2+2n+1+2n+2+1 \) | |
| \( = n^2 +4n + 4. \) |
\(((n+1)+1)^2 = (n+2)^2 = n^2+4n+4.\)
Poiché se vale \(P(n)\) allora sia \(\sum_{i = 0}^{n+1} 2 i + 1\) che \(( (n+1) + 1 )^2\) sono uguali a \(n^2+4n+4\), si ha che anche \(P(n+1)\) è vera.
Dimostrare che \(\sum_{i=0}^n 2i = n^2+n\) per ogni \(n \in \mathbb{N}\).
Per induzione su \(n \geq 0\).
Caso base: \(\sum_{i=0}^0 2i = 2 \cdot 0 = 0 = 0^2 + 0\) (\(n=0\))
Passo induttivo: Data \(\sum_{i=0}^n 2i = n^2+n\) dimostriamo che
\(\sum_{i=0}^{n+1} 2i = (n+1)^2+(n+1)\).
| \( \sum_{i=0}^{n+1} 2i \) | \( = \sum_{i=0}^n 2i + 2(n+1) \) |
|---|---|
| \( = n^2+n + 2(n+1) \text{ [per ipotesi induttiva]} \) | |
| \( = n^2 + n + 2n + 2 \) | |
| \( = (n^2 + 2n + 1) + (n + 1) \) | |
| \( = (n+1)^2 + (n+1) \) |
Dimostrare che per ogni \(n \geq 1\)
\[\sum_{i=1}^n (2i)^3 = 2 n^2(n+1)^2.\]
Attenzione! In questo caso il passo base è quello per \(n = 1\) (il passo induttivo resta invariato).
(Soluzione alla lavagna)
Ricordiamo che dato \(n \geq 1\), \[n! = \prod_{i=1}^n i = 1 \cdot 2\cdot \dotsc \cdot n .\]
Dimostrare che \(2^n < n!\) per ogni \(n \geq 4\).
Per induzione su \(n \geq 4\).
Caso base: \(2^4 = 16 < 24 = 1 \cdot 2 \cdot 3 \cdot 4 = 4!\) (\(n=4\))
Passo induttivo: Data \(2^n < n!\) dimostrare che \(2^{n+1} < (n+1)!\).
| \( 2^{n+1} \) | \( = 2^n \cdot 2 \) |
|---|---|
| \( < n! \cdot 2 \text{ [per ipotesi induttiva]} \) | |
| \( < n! \cdot (n+1) \text{ [perché} n \geq 4 \text{ e } n! \geq 1 \text{]} \) | |
| \( = (n+1)! \) |
Definiamo la successione \((a_{n})_{n \in \mathbb{N}}\) per ricorrenza ponendo \[\begin{cases} a_{0} = 1 , \\ a_{n+1} = 2 \cdot a_{n}+1. \end{cases}\]
Dimostrare che \(a_{n} = 2^{n+1}-1\) per ogni \(n \in \mathbb{N}\).
Per induzione su \(n \geq 0\).
Caso base: \(a_{0} = 1 = 2^{0+1}-1\) (\(n=0\))
Passo induttivo: Data \(a_{n} = 2^{n+1}-1\) dimostrare che \(a_{n+1} = 2^{(n+1)+1}-1\).
| \( a_{n+1} \) | \( = 2 \cdot a_{n} + 1 \) |
|---|---|
| \( = 2 \cdot (2^{n+1}-1) + 1 \text{ [per ipotesi induttiva]} \) | |
| \( = 2 \cdot 2^{n+1} - 2 + 1 \) | |
| \( = 2^{n+2} -1 \) | |
| \( = 2^{(n+1)+1} -1 \) |
Definiamo \(g \colon \mathbb{N} \to \mathbb{N}\) per ricorsione ponendo \[\begin{cases} g(0) = 2, \\ g(n+1) = g(n) \cdot g(n). \end{cases}\]
Dimostrare che \(g(n) = 2^{(2^n)}\) per ogni \(n \in \mathbb{N}\).
Per induzione su \(n \geq 0\).
Caso base: \(g(0) = 2 = 2^1 = 2^{(2^0)}\) (\(n=0\))
Passo induttivo: Data \(g(n) = 2^{(2^n)}\) dimostrare che \(g(n+1) = 2^{(2^{n+1})}\)
| \( g(n+1) \) | \( = g(n) \cdot g(n) \) |
|---|---|
| \( = 2^{(2^n)} \cdot 2^{(2^n)} \text{ [per ipotesi induttiva]} \) | |
| \( = 2^{(2^n+2^n)} \) | |
| \( = 2^{(2 \cdot 2^n)} \) | |
| \( = 2^{(2^{n+1})} \) | |
| \( = (\underbrace{2 \cdot 2 \cdot \dotsc \cdot 2}_{2^n \text{ volte}}) \cdot (\underbrace{2 \cdot 2 \cdot \dotsc \cdot 2}_{2^n \text{ volte}}) \) | |
| \( = \underbrace{2 \cdot 2 \cdot \dotsc \cdot 2}_{2 \cdot 2^n \text{ volte}} \) | |
| \( = \underbrace{2 \cdot 2 \cdot \dotsc \cdot 2}_{2^{n+1} \text{ volte}} \) | |
| \( = 2^{(2^{n+1})} \) |
Sia \(X\) un insieme infinito e \(f \colon X \times X \to X\) una biezione. Definiamo una successione di funzioni \((h_{n})_{n \in \mathbb{N}}\) per ricorrenza ponendo: \[\begin{cases} h_{2} \colon X^2 \to X, & \quad (x_{1}, x_{2}) \mapsto f(x_{1}, x_{2}), \\ h_{n+1} \colon X^{n+1} \to X, & \quad (x_{1}, \dotsc, x_{n+1}) \mapsto f(h_{n}(x_{1}, \dotsc, x_{n}),x_{n+1}). \end{cases}\]
Dimostrare che \(h_{n} \colon X^n \to X\) è una biezione per ogni \(n \geq 2\).
Per induzione su \(n \geq 2\).
Caso base (\(n=2\)): si ha \(h_{2} = f\), quindi \(h_{2}\) è una biezione poiché \(f\) lo è.
Passo induttivo: Iniettività. se \(h_{n+1}(x_{1}, \dotsc, x_{n+1}) = h_{n+1}(y_{1}, \dotsc, y_{n+1})\), allora \(x_{n+1} = y_{n+1}\) e \(h_{n}(x_{1}, \dotsc, x_{n}) = h_{n}(y_{1}, \dotsc, y_{n})\) poiché \(f\) è iniettiva. Ma allora anche \((x_{1}, \dotsc, x_{n}) = (y_{1}, \dotsc, y_{n})\) perché, per ipotesi induttiva, \(h_{n}\) è iniettiva. Quindi \((x_{1}, \dotsc, x_{n+1} ) = (y_{1}, \dotsc, y_{n+1})\).
Suriettività. Dato \(y \in X\), esistono \(x,z \in X\) tali che \(f(x,z) = y\) poiché \(f\) è suriettiva. Poiché per ipotesi induttiva \(h_{n}\) è suriettiva, esiste \((x_{1}, \dotsc, x_{n}) \in X^n\) tale che \(h_{n}(x_{1}, \dotsc, x_{n}) = x\). Ponendo \(x_{n+1} = z\) si ha allora \(h_{n+1} (x_{1}, \dotsc, x_{n+1}) = f(h_{n}(x_{1}, \dotsc, x_{n}),x_{n+1}) = f(x,z) = y\).
Dimostrare che ogni affrancatura da \(4\) centesimi o più può essere ottenuta usando solo francobolli da \(2\) e \(5\) centesimi.
(Soluzione alla lavagna)
Dimostrare per induzione che se \(n\) è dispari e \(a_{1} , \dots , a_{n}\) sono dispari, allora \(\sum_{i = 1}^n a_{i}\) è dispari.
(Soluzione alla lavagna)